package hot100;

public class Solution200 {

    class UnionFind {

        private int count;
        private int[] parent;

        public UnionFind(int count) {
            this.count = count;
            parent = new int[count];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            parent[rootX] = rootY;
            count--;
        }
    }

    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        UnionFind unionFind = new UnionFind(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0') {
                    continue;
                }
                if (i > 0 && grid[i - 1][j] == '1') {
                    unionFind.union(i * n + j, (i - 1) * n + j);
                }
                if (i < m - 1 && grid[i + 1][j] == '1') {
                    unionFind.union(i * n + j, (i + 1) * n + j);
                }
                if (j > 0 && grid[i][j - 1] == '1') {
                    unionFind.union(i * n + j, i * n + j - 1);
                }
                if (j < n - 1 && grid[i][j + 1] == '1') {
                    unionFind.union(i * n + j, i * n + j + 1);
                }
            }
        }
        return unionFind.count;
    }

    public static void main(String[] args) {
        Solution200 solution200 = new Solution200();
        char[][] grid = new char[][]{
            {'1', '1', '1', '1', '0'},
            {'1', '1', '0', '1', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '0', '0', '0'},
        };
        solution200.numIslands(grid);
    }
}
